/*
 * @lc app=leetcode.cn id=153 lang=cpp
 * @lcpr version=30204
 *
 * [153] 寻找旋转排序数组中的最小值
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    int findMin(vector<int> &nums)
    {
        // 法一：
        // int n = nums.size();
        // if (n == 0)
        // {
        //     return -1;
        // }
        // if (n == 1)
        // {
        //     return nums[0];
        // }

        // int left = 0;
        // int right = n - 1;
        // while (left < right)
        // {
        //     int mid = (left + right) >> 1;
        //     if (nums[left] > nums[right])
        //     {
        //         if (nums[left] < nums[mid])
        //         {
        //             // 说明left到mid这一段是大区间
        //             left = mid + 1;
        //         }
        //         else if (nums[left] > nums[mid])
        //         {
        //             // mid到right是小区间，且mid < right，但无法确定mid是不是最小值
        //             right = mid;
        //         }
        //         else
        //         {
        //             // left = mid，
        //             if (nums[left] < nums[right])
        //             {
        //                 return nums[left];
        //             }
        //             else
        //             {
        //                 return nums[right];
        //             }
        //         }
        //     }
        //     else
        //     {
        //         return nums[left];
        //     }
        // }
        // return nums[left];

        // 法二：
        int left = 0;
        int right = nums.size() - 1;
        while (left < right)
        {
            int mid = (left + right) >> 1;
            if (nums[mid] < nums[right])
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        return nums[left];
    }
};
// @lc code=end

/*
// @lcpr case=start
// [3,4,5,1,2]\n
// @lcpr case=end

// @lcpr case=start
// [4,5,6,7,0,1,2]\n
// @lcpr case=end

// @lcpr case=start
// [11,13,15,17]\n
// @lcpr case=end

 */
